
//1210.穿过迷宫的最小移动次数
class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        //使用BFS,只需要记录蛇身的方向
        int n=grid.size(),m=grid[0].size(),step=0;
        const int RIGHT=1;
        const int DOWN=2;
        queue<vector<int>> q;
        q.push({0,1,RIGHT});
        vector<vector<vector<int>>> vist(n,vector<vector<int>>(m,vector<int>(2)));//使用两个变量其中0表示竖直方向,1表示水平方向
        vist[0][1][1]=1;
        while(!q.empty())
        {
            int _size=q.size();
            for(int i=0;i<_size;i++)
            {
                int x=q.front()[0],y=q.front()[1],dir=q.front()[2];
                q.pop();
                if(x==n-1&&y==n-1&&dir==RIGHT) return step;
                if(dir==RIGHT)
                {
                    //向右
                    if(y+1<m&&!grid[x][y+1]&&!vist[x][y+1][1]) 
                    {
                        q.push({x,y+1,RIGHT});
                        vist[x][y+1][1]=1;
                    }
                    //旋转
                    if(x + 1 < n && !grid[x + 1][y] && !grid[x + 1][y-1]&&!vist[x+1][y-1][0])
                    {
                        q.push({x+1,y-1,DOWN}); 
                        vist[x+1][y-1][0]=1;
                    }
                    //整体向下移动
                    if(x+1<n&&!grid[x+1][y-1]&&!grid[x+1][y]&&!vist[x+1][y][1]) 
                    {
                        q.push({x+1,y,RIGHT});
                        vist[x+1][y][1]=1;
                    }
                }
                else
                {
                    if(x+1<n&&!grid[x+1][y]&&!vist[x+1][y][0]) 
                    {
                        q.push({x+1,y,DOWN});
                        vist[x+1][y][0]=1;
                    }
                    if(y+1<m&&!grid[x][y+1]&&!grid[x-1][y+1]&&!vist[x-1][y+1][1])
                    {
                        q.push({x-1,y+1,RIGHT}); 
                        vist[x-1][y+1][1]=1;
                    }
                    //整体向右
                    if(y+1<n&&!grid[x-1][y+1]&&!grid[x][y+1]&&!vist[x][y+1][0]) 
                    {
                        q.push({x,y+1,DOWN});
                        vist[x][y+1][0]=1;
                    }
                }
            }
            step++;
        }
        return -1;
    }
};